#include <assert.h>
#include <string.h>
#include <stdlib.h>
// proj
#include "zset.h"
#include "common.h"

/**
 * @brief 创建新的有序集合节点
 * @param name 元素名称
 * @param len 名称长度
 * @param score 分数
 * @return 新创建的节点指针
 */
static ZNode *znode_new(const char *name, size_t len, double score) 
{
    ZNode *node = (ZNode *)malloc(sizeof(ZNode) + len);
    assert(node);   // 在实际项目中不是好主意
    avl_init(&node->tree);
    node->hmap.next = NULL;
    node->hmap.hcode = str_hash((uint8_t *)name, len);
    node->score = score;
    node->len = len;
    memcpy(&node->name[0], name, len);
    return node;
}

/**
 * @brief 删除ZNode节点
 */
void znode_del(ZNode *node) 
{
    delete node;
}

/**
 * @brief 取较小值
 * @param lhs 左值
 * @param rhs 右值
 * @return 较小的值
 */
static size_t min(size_t lhs, size_t rhs) 
{
    return lhs < rhs ? lhs : rhs;
}

/**
 * @brief 按(score, name)元组比较
 * @param lhs AVL树节点
 * @param score 分数
 * @param name 名称
 * @param len 名称长度
 * @return 如果lhs < (score, name)返回true
 */
static bool zless(
    AVLNode *lhs, double score, const char *name, size_t len)
{
    ZNode *zl = container_of(lhs, ZNode, tree);
    if (zl->score != score) {
        return zl->score < score;
    }
    int rv = memcmp(zl->name, name, min(zl->len, len));
    if (rv != 0) {
        return rv < 0;
    }
    return zl->len < len;
}

/**
 * @brief 比较两个AVL树节点
 * @param lhs 左节点
 * @param rhs 右节点
 * @return 如果lhs < rhs返回true
 */
static bool zless(AVLNode *lhs, AVLNode *rhs) 
{
    ZNode *zr = container_of(rhs, ZNode, tree);
    return zless(lhs, zr->score, zr->name, zr->len);
}

/**
 * @brief 向AVL树中插入节点
 * @param zset 有序集合指针
 * @param node 要插入的节点
 */
static void tree_insert(ZSet *zset, ZNode *node) 
{
    AVLNode *parent = NULL;         // 在此节点下插入
    AVLNode **from = &zset->root;   // 指向下一个节点的传入指针
    while (*from) 
    {                 // 树搜索
        parent = *from;
        from = zless(&node->tree, parent) ? &parent->left : &parent->right;
    }
    *from = &node->tree;            // 附加新节点
    node->tree.parent = parent;
    zset->root = avl_fix(&node->tree);
}

/**
 * @brief 更新现有节点的分数
 * @param zset 有序集合指针
 * @param node 要更新的节点
 * @param score 新分数
 */
static void zset_update(ZSet *zset, ZNode *node, double score) 
{
    if (node->score == score) 
    {
        return;
    }
    // 分离树节点
    zset->root = avl_del(&node->tree);
    avl_init(&node->tree);
    // 重新插入树节点
    node->score = score;
    tree_insert(zset, node);
}

bool zset_insert(ZSet *zset, const char *name, size_t len, double score) 
{
    ZNode *node = zset_lookup(zset, name, len);
    if (node) 
    {
        zset_update(zset, node, score);
        return false;
    } 
    else 
    {
        node = znode_new(name, len, score);
        hm_insert(&zset->hmap, &node->hmap);
        tree_insert(zset, node);
        return true;
    }
}

/**
 * @brief 哈希表查找的辅助结构
 */
struct HKey 
{
    HNode node;
    const char *name;
    size_t len;
};

/**
 * @brief 哈希表比较函数
 * @param node 哈希表节点
 * @param key 查找键
 * @return 如果相等返回true
 */
static bool hcmp(HNode *node, HNode *key) 
{
    ZNode *znode = container_of(node, ZNode, hmap);
    HKey *hkey = container_of(key, HKey, node);
    if (znode->len != hkey->len) 
    {
        return false;
    }
    return memcmp(znode->name, hkey->name, znode->len) == 0;
}

ZNode *zset_lookup(ZSet *zset, const char *name, size_t len) 
{
    if (!zset->root) 
    {
        return NULL;
    }

    HKey key;
    key.node.hcode = str_hash((uint8_t *)name, len);
    key.name = name;
    key.len = len;
    HNode *found = hm_lookup(&zset->hmap, &key.node, &hcmp);
    return found ? container_of(found, ZNode, hmap) : NULL;
}

void zset_delete(ZSet *zset, ZNode *node) 
{
    // 从哈希表中移除
    HKey key;
    key.node.hcode = node->hmap.hcode;
    key.name = node->name;
    key.len = node->len;
    HNode *found = hm_delete(&zset->hmap, &key.node, &hcmp);
    assert(found);
    
    // 从树中移除
    zset->root = avl_del(&node->tree);
    
    // 释放节点
    znode_del(node);
}

ZNode *zset_seekge(ZSet *zset, double score, const char *name, size_t len) 
{
    AVLNode *found = NULL;
    for (AVLNode *node = zset->root; node; ) 
    {
        if (zless(node, score, name, len)) 
        {
            node = node->right; // node < key
        } 
        else 
        {
            found = node;       // 候选
            node = node->left;
        }
    }
    return found ? container_of(found, ZNode, tree) : NULL;
}

ZNode *znode_offset(ZNode *node, int64_t offset) 
{
    AVLNode *tnode = node ? avl_offset(&node->tree, offset) : NULL;
    return tnode ? container_of(tnode, ZNode, tree) : NULL;
}

/**
 * @brief 递归销毁树
 * @param node 要销毁的节点
 */
static void tree_dispose(AVLNode *node) 
{
    if (!node) 
    {
        return;
    }
    tree_dispose(node->left);
    tree_dispose(node->right);
    znode_del(container_of(node, ZNode, tree));
}

void zset_clear(ZSet *zset) 
{
    hm_clear(&zset->hmap);
    tree_dispose(zset->root);
    zset->root = NULL;
}

bool zset_add(ZSet *zset, const char *name, size_t len, double score) 
{
    return zset_insert(zset, name, len, score);
}

void zset_new(ZSet *zset) 
{
    zset->root = NULL;
    hm_init(&zset->hmap);
}

ZNode *zset_pop(ZSet *zset, const char *name, size_t len) 
{
    ZNode *node = zset_lookup(zset, name, len);
    if (node) 
    {
        // 从哈希表中移除
        HKey key;
        key.node.hcode = str_hash((uint8_t *)name, len);
        key.name = name;
        key.len = len;
        HNode *found = hm_delete(&zset->hmap, &key.node, &hcmp);
        assert(found);
        
        // 从树中移除
        zset->root = avl_del(&node->tree);
        
        return node;
    }
    return NULL;
}

ZNode *zset_query(ZSet *zset, double score, const char *name, size_t len) 
{
    return zset_seekge(zset, score, name, len);
}

void zset_dispose(ZSet *zset) 
{
    zset_clear(zset);
} 